Solving 10385 - Duathlon (Ternary search)
[andmenj-acm.git] / 610 - Street directions / 610.cpp
blobaba951bb8e2d06f82ae86dbc2488aacaa395ab94
1 /*
2 Problem: 610 - Street directions (UVa online judge)
4 Author: Andrés Mejía-Posada (http://github.com/andmej/acm)
5 Algorithm: Depth-first search
6 */
7 #include <iostream>
9 using namespace std;
11 const int MAXN = 1000;
13 bool g[MAXN][MAXN], visited[MAXN];
14 int n, p[MAXN]; //p[i] = nodo predecesor que me llevó al nodo i.
16 void dfs(int u){
17 visited[u] = true;
18 for (int v=0; v<n; ++v){
19 if (g[u][v]){ //hay arista
20 if (visited[v] && v != p[u]){ //encontre un ciclo
21 g[v][u] = false;
22 int previous = u;
23 while(previous != v){ //Volver de una sola vía todas las aristas del ciclo
24 g[previous][p[previous]] = false;
25 previous = p[previous];
27 }else if (!visited[v]){
28 p[v] = u;
29 dfs(v);
35 int main(){
36 int m, C=1;
37 while (scanf("%d %d", &n, &m) == 2 && (n+m)){
38 for (int i=0; i<n; ++i){
39 for (int j=0; j<n; ++j){
40 g[i][j] = false;
42 visited[i] = false;
43 p[i] = -1;
46 int u, v;
47 while (m--){
48 scanf("%d %d", &u, &v);
49 --u, --v;
50 g[u][v] = g[v][u] = true;
53 dfs(0);
54 printf("%d\n\n", C++);
55 for(int i=0; i<n; ++i){
56 for (int j=0; j<n; ++j){
57 if (g[i][j]){
58 printf("%d %d\n", i+1, j+1);
62 printf("#\n");
65 return 0;